//
//  Combine.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/9/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  77. 组合

import UIKit

/*
 77. 组合
 
 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

 示例:

 输入: n = 4, k = 2
 输出:
 [
   [2,4],
   [3,4],
   [2,3],
   [1,2],
   [1,3],
   [1,4],
 ]
 */

class Combine: NSObject {
    
    var resultArr:[[Int]] = []
    
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        guard n > 1 else {
            return [[n]]
        }
        
        var sourceArr = [Int]()
        for i in 1 ... n{
            sourceArr.append(i)
        }
        
        self.dfs(0, [], sourceArr, k)
        return resultArr
    }
    
    func dfs(_ startIndex: Int, _ tmpArr: [Int], _ sourceArr: [Int], _ k: Int){
        
        var tmpArr = tmpArr
        if tmpArr.count == k {
            resultArr.append(tmpArr)
            return
        }
        for i in startIndex ..< sourceArr.count{
            tmpArr.append(sourceArr[i])
            self.dfs(i+1, tmpArr, sourceArr, k)
            tmpArr.removeLast()
        }
    }
}
